1308. Наибольшая грань подстроки

Гранью (border, verge, brink) br строки S называется любой собственный префикс этой строки, равный суффиксу S.

Строка S = abaababaabaab имеет две грани (не пустые) - ab и abaab. Строка S = abaabaab также имеет две грани – ab и abaab, но вторая грань – перекрывающаяся. Строка длины n из повторяющегося символа, например aaaaaaaa (или a⁸), имеет n – 1 грань. Для S = a⁸ это грани: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa.

Понятие "собственный префикс" исключает грань, совпадающую с самой строкой.

Длина грани – это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок S[1..i] (i = 1..n) и сохранить их в массиве br[1..n].

Найдите наибольшее значение грани в массиве наибольших граней br для всех подстрок S.

Вход. Дана строка S (|S| ≤ 10⁶).

Выход. В единственной строке вывести ответ поставленной задачи.

Пример входа

abaabaab

Пример выхода

5

РЕШЕНИЕ

строки – префикс-функция

Анализ алгоритма

Построим для строки S в массиве p префикс-функцию. Для решения задачи достаточно найти максимальное значение среди всех p[i] (0 ≤ i < n).

Реализация алгоритма

Входная строка s содержит не более MAX = 1000010 символов. Префикс-функцию строки s сохраняем в векторе p.

#define MAX 1000010

char s[MAX];

vector<int> p;

Строим префикс-функцию для строки s длины n при помощи функции MaxBorderArray. Вычисляем длину наибольшей грани среди всех граней подстрок S в переменной res.

gets(s); n = strlen(s);

p = MaxBorderArray(s);

for(i = 1; i < n; i++)

if (res < p[i]) res = p[i];

printf("%d\n",res);